Assume for the sake of contradiction that we have an $\epsilon_1$-approximate personalized equilibrium that does not satisfy some constraint of the program to within $\epsilon_2$. Let $w_i(e)$ = the weight placed by player $i$ on edge $e$ in this approximate equilibrium. The first three constraints of program \ref{lp_with_mins} must be satisfied to within $\epsilon_1$, since they are the definition of a feasible weight assignment. Therefore, assume this equilibrium does not satisfy the $\min$ constraint to within $\epsilon_2$ for some player $i$ and some subset $F \subseteq E_i$ for which LP \ref{non_optimal_lp} is feasible. 

Consider a solution $\delta^*$ for LP \ref{non_optimal_lp} for this $i$ and $F$. Let $M = \frac{\epsilon_2}{\max_{e \in F} |\delta^*(e)|}$, and let $\delta'(e) = \delta^*(e) \cdot M$. We know that $M$ is well-defined since $\delta^*(e) < 0$ for all $e \in F$. Furthermore, for all $e$ with $\delta(e)<0$ (i.e., for all $e \in F$), $|\delta'(e)| \leq \epsilon_2 \leq w_i(e)$. 

Now consider the following slightly adjusted linear program.
$$
\textrm{maximize } \sum_{e \in E_i} \delta(e)u_i(e)
$$
\begin{alignat}{2}
\sum_{e: s \in e} \delta(e) & = 0 && s \in S_j, 1 \le j \le k, j \neq i \label{new_lp} \\
\delta(e) & \geq -\epsilon_2 \qquad && (e \in F) \nonumber \\
\delta(e) & \geq 0 && (e \notin F) \nonumber
\end{alignat}

By our choice of $\delta'$ and the analysis above, $\delta'$ obeys each constraint of the new linear program \ref{new_lp}, and $\delta'$ gives a maximization value greater than $0$. LP \ref{new_lp} has $|E_i| \leq |E|$ variables, each coefficient $u_i(e)$ can be represented as $\frac{a}{b}$ for $\beta$-bit integers $a$ and $b$, and coefficient $\epsilon_2 = \frac{1}{d}$ for $\gamma$ bit integer $d$. Some optimal solution of an LP will be located at a vertex, so by Corollary \ref{lp_vertex_precision}, each dimension of this optimal solution of LP \ref{new_lp} will be representable by $\frac{c}{b}$ for integers $c$ and $d$, each of less than $3|E|(\beta+\gamma)$ bits. 

Let $\delta$ = the solution to LP \ref{new_lp}, and consider the alternate assignment for player $i$ specified by $w^*_i(e) = w_i(e) + \delta(e)$.  By the first constraint of LP \ref{new_lp}, this still does not overfill or underfill any strategy by more than $\epsilon_1$, and player $i$ still places total weight between $1 - \epsilon_1$ and $1 + \epsilon_1$. By the second and third constraints, $\delta(e) < 0$ if and only if $e \in F$, in which case $|\delta(e)| \leq \epsilon_2$ (when $w_i(e) \geq \epsilon_2$), so $w^*_i(e) \geq 0$. In other words, we still have a valid weight assignment for an $\epsilon_1$-approximate personalized equilibrium. Since we know LP \ref{new_lp} has a solution $>0$, and (from above) each coordinate of the solution is representable as $\frac{c}{d}$ for integers $c$ and $d$, where each of $c$ and $d$ is representable by at most $3|E|(\beta + \gamma)$ bits, this gives a total utility for player $i$ that is more than $\frac{1}{2^{3|E|(\beta + \gamma)}} = \epsilon_1$ larger than the original total utility.  Therefore, the original solution was not a valid $\epsilon_1$-approximate personalized equilibrium, contradicting our assumption and completing the proof.